[OI 基础] 数据结构与算法 - 最短路径和最小生成树

发表于 | 更新于 | 分类于

数据结构与算法 - 最短路径和最小生成树(Day4)

  • 最短路径

    • 在带权图G=(V.E)中, 若顶点Vi, Vj是图G的两个顶点, 从顶点Vi到Vj的路径长度定义为路径上各条边的权值之和. 从顶点Vi到Vj可能有多条路径, 其中路径长度最小的称为顶点Vi到Vj的最短路径

    • 最短路问题

      • 求从某个顶点到其他顶点的最短路径
        • dijkstra算法
        • Bellman-ford算法
        • SPFA算法
      • 求图中每一对顶点间的最短路径
        • 弗洛伊德算法(Floyed)

    • 对于无权图, 可把每条边的权值设置为1处理.

    • 算法

      • 弗洛伊德算法

        • 若图中任意两点之间只允许编号<=k-1的点作为中转时的最短路已知
        • 可依此推出任意两点之间只允许以编号<=k的点做中转的最短路
        1
        2
        if(d[i][k] + d[k][j] < d[i][j])	//d[i][k]的路径长度和d[k][j]的路径长度之和小于ij之间路径
          d[i][j] = d[i][k] + d[k][j];//升级ij路径为更短的
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        //算法核心
        for(int k = 1; k<=n; k++)
          for(int i = 1; i <= n; i++)
            for(int j = 1;j <= n; i++)
              if(d[i][k] + d[k][j] < d[i][j])
          		d[i][j] = d[i][k] + d[k][j];
        //初始化条件
        d[i][i] = 0;
        d[i][j] = 边权(若i,j之间直接相连);
        d[i][j] = ∞  (若i,j无直接相连的边);

      • Dijkstra算法

        • 求一个顶点到其余各定点的最短路径

        • 算法思路

          • 设起点为s, dis[v]表示从s到v的最短路径, path[v]为v的前驱节点, 用来输出路径
          1. 初始化: dis[v]=∞(v≠s); dis[s]=0; path[s]=0;
          2. for i = 1 to n
            1. 在没有被标记的点找一个顶点u使得dis[u]是最小的
            2. u标记为已确定的最短路径
            3. 循环: 与u相连的每个未确定最短路径的顶点v
              1. 若dis[u]+Weight(u,v) < dis[v]
                1. dis[v] = dis[u] + Weight(u,v);
                2. path[v] = u;

        • 使用条件

          • 不存在边权为负数的情况(不存在负权边)
        1
        2
        3
        4
        5
        6
        7
        8
        9
        10
        11
        12
        13
        14
        15
        16
        17
        18
        19
        20
        21
        22
        23
        24
        25
        26
        27
        28
        29
        void dijkstra(int s){
          for(int i = 1;i<=n;i++){	//初始化
            d[i] = a[s][i];	//d[i]初始化成i到s的长度
            f[i] = false;	//f[i]标志位初始化为false
            path[i] = s;	//i的前驱结点为起点
          }
          
          f[s] = true;	//标记起点
          
          for(int i = 2;i<=n;i++){
            int mind = inf;	//inf = 0x7f
            int k = 0;	//记录准备标记的点
            for(int j = 1;j<=n;j++){
              if(!f[j] && (d[j] < mind)){
                mind = d[j]; k = j;
              }
              if(mind == inf)
                break;//无连接到j的点, 无法更新
              
              f[k] = true;
              
              for(int j = 1; j<=n; j++)
                if((!f[j]) && (d[k] + a[k][j] < d[j])){
                  d[j] = d[k] + a[k][j];
                  path[j] = k;
                }
            }
          }
        }

        ​

    • 最小生成树

      • N个点用N-1条边连接成一个连通块, 形成的图形只可能是树.
      • 一个有N个点的图, 边一定大于等于N-1条
      • 图的最小生成树就是在这些边中选择N-1条, 连接所有的N个点. 这N-1条边的边权之和是所有方案中最小的
      • 生成算法
        • Prim算法
          • 待续
        • Kruskal算法
          • 待续